/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/check-sum-of-k-primes
   @Language: C++
   @Datetime: 20-01-19 17:43
   */

class Solution {
public:
	/**
	 * @param n: an int
	 * @param k: an int
	 * @return: if N can be expressed in the form of sum of K primes, return true; otherwise, return false.
	 * Goldbach Conjecture: n>5 ==> n == sum of 3 primes;
	 *            n>2 && n%2==0 ==> n == sum of 2 primes.
	 */
	bool isSumOfKPrimes(int n, int k) {
		// write your code here
		auto isPrime = [](int x)->bool{
			for(int i=2; i*i<=x; ++i)
				if (x%i==0) return false;
			return true;
		};
		if (k==0 || n<2*k) return false;
		if (k==1) return isPrime(n);
		if (k==2) return n%2==0 || isPrime(n-2);
		return true;
	}
};
